incompressible string

Definition

A string $x$ is incompressible or Kolmogorov random if $K(x) \geq \lvert x \rvert$.
(where $K(x)$ is Kolmogorov complexity)

Theorem

It is undecidable whether a string is incompressible.

References

1. https://www.cs.cmu.edu/~venkatg/teaching/15252-sp20/notes/Kolmogorov-Complexity.pdf